package com.ting.test.algorithms.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 完全二叉树的概念:
 * 1. 完全二叉树的每一层一定是满的
 * 2. 如果有不满的一层，那一定是最后一层不满
 * 3. 不满的那一层也是从左到右都是满的，只有最后一个节点可能不满
 * <p>
 * 利用层序遍历的思路:
 * 1. 如果某一个节点 有右孩子没有左孩子 或者有左孩子没有右孩子 一定不是完全二叉树
 */
public class 判断是完全二叉树 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        boolean result = isBSt(head);
        System.out.println(result);
    }

    private static boolean isBSt(TreeNode head) {

        if (null == head) {//空节点认为是满二叉树
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        // 是否遇到过 左右两个子节点不双全的节点
        boolean flag = false;
        queue.add(head);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            TreeNode leftNode = poll.left;
            TreeNode rightNode = poll.right;

            // 如果有一个节点 有右孩子 没有左孩子 一定不是完全二叉树 直接返回
            if (leftNode == null && rightNode != null) {
                return false;
            }
            //出现了左右两个子节点不双全的节点
            if (leftNode == null && rightNode == null) {
                flag = true;
            }

            // 如果之前已经发现过一个左右两个孩子不双全的情况
            // 现在又出现一个非叶子节点，则肯定不是完全二叉树
            if (flag && (rightNode != null || leftNode != null)) {
                return false;
            }

            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return flag;
    }

}
